// Classe que define uma trie (apenas para strings)

#ifndef Trie_hpp
#define Trie_hpp

#include <list>
#include <vector>
#include <ostream>
#include <istream>
#include <string>

class Trie {
	// Verdadeiro se o no possui valores
	bool						 values;
	// Filhos do no
	std::vector<Trie *>          children;
	// Quantidade de filhos do no
	int 						 qtyChildren;
	// Pai do no (0 caso raiz)
	Trie*						 dad;
	// Letra pela qual o no' foi conectado ao pai
	char 						 dadConnection;
public:
	// Construtor
	Trie(Trie* dad = 0, char dadConnection = -1);
	// Destrutor
	virtual ~Trie();
	// Insere uma palavra
	void  insert(std::string& word);
	void  insert(const char * word);

	// Retorna um ponteiro para o no que contenha a palavra ou 
	// null caso ele nao exista
	Trie* retrieve(std::string word);
	Trie* retrieve(const char * word);

	// Retorna um ponteiro para o no que contenha um prefixo
	// da palavra e modifica a palavra para seu prefixo, ou
	// null caso nao exista
	Trie* retrieveUntil(std::string& word);
	Trie* retrieveUntil(char * word);

	// Serializa a trie
	void  serialize(std::ostream& stream, int head = 0);

	// Deserializa a trie
	int   deserialize(std::istream& stream);

	// Remove a palavra que o no representa da trie ao qual
	// ele esta relacionado, e os nos que se tornaram
	// inuteis
	void  remove();

	// Converte o conteudo da trie em uma lista
	template <typename T>
	void itemize(T& container, std::string path = std::string());
	

	// Metodos de suporte
	static int convertToIndice(char letter);
	static char convertToChar(int pos);
};

#include <Trie.inl>

#endif
